﻿#ifndef XMULTIWAYTREE_H
#define XMULTIWAYTREE_H
#include<vector>
#include<stack>
//多叉树
template<typename Ty>
class XMultiWayTree
{
public:
	XMultiWayTree(XMultiWayTree<Ty>* parent=nullptr);
	XMultiWayTree(const size_t childCount, const size_t dataCount=1, XMultiWayTree<Ty>* parent = nullptr);
	virtual ~XMultiWayTree();
	//设置父节点
	void setParent(XMultiWayTree<Ty>* parent);
	//获取父节点指针
	const XMultiWayTree<Ty>* parent()const;
public:
	//添加一个孩子节点
	void addChild(XMultiWayTree<Ty>* node);
	//获取一个孩子节点
	 XMultiWayTree<Ty>* child(const size_t nSel = 0);
	//设置孩子节点
	void setChild(XMultiWayTree<Ty>* node, const size_t nSel = 0);
	//获取孩子数量
	const size_t childSize()const;
	//获取全部孩子节点
	const std::vector<XMultiWayTree<Ty>*>& childs()const;
	//删除孩子节点
	const bool removeChild(XMultiWayTree<Ty>* node);
	const bool removeChild(const size_t nSel=0);
	
public:
	//添加一个数据
	void addData(const Ty& data);
	//获取一个数据
	Ty data(const size_t nSel=0)const;
	//获取数据数量
	const size_t dataSize()const;
	//获取全部数据
	const std::vector<Ty>& datas()const;
	//设置数据
	void setData(const Ty& data, const size_t nSel = 0);
	//删除数据
	const bool removeData(Ty& data);
	const bool removeData(const size_t nSel = 0);
public:
	//清空树只剩下自己(递归的方式清空自己的全部孩子)
	void clearTree()const;
	//清空树包括自己
	static void clearTree(XMultiWayTree<Ty>* root);
protected:
	//孩子索引是否合法存在
	bool isChildIndex(const size_t nSel = 0)const;
	//数据索引是否合法存在
	bool isDataIndex(const size_t nSel = 0)const;
protected:
	std::vector<Ty> m_DataList;//数据列表
	XMultiWayTree<Ty>* m_parent;//父节点
	std::vector<XMultiWayTree<Ty>*>m_ChildList;//孩子节点列表
};


template<typename Ty>
inline XMultiWayTree<Ty>::XMultiWayTree(XMultiWayTree<Ty>* parent)
	:m_parent(parent)
{

}

template<typename Ty>
inline XMultiWayTree<Ty>::XMultiWayTree(const size_t childCount, const size_t dataCount, XMultiWayTree<Ty>* parent)
	:m_parent(parent)
{
	m_DataList.resize(dataCount);
	m_ChildList.resize(childCount);
}

template<typename Ty>
inline XMultiWayTree<Ty>::~XMultiWayTree()
{
}
template<typename Ty>
inline void XMultiWayTree<Ty>::setParent(XMultiWayTree<Ty>* parent)
{
	m_parent = parent;
}
template<typename Ty>
inline const XMultiWayTree<Ty>* XMultiWayTree<Ty>::parent() const
{
	return m_parent;
}
template<typename Ty>
inline void XMultiWayTree<Ty>::addChild(XMultiWayTree<Ty>* node)
{
	m_ChildList.push_back(node);
}
template<typename Ty>
inline  XMultiWayTree<Ty>* XMultiWayTree<Ty>::child(const size_t nSel)
{
	if (!isChildIndex(nSel))
		return nullptr;
	return m_ChildList[nSel];
}
template<typename Ty>
inline const size_t XMultiWayTree<Ty>::childSize() const
{
	return m_ChildList.size();
}
template<typename Ty>
inline const std::vector<XMultiWayTree<Ty>*>& XMultiWayTree<Ty>::childs() const
{
	return m_ChildList;
}
template<typename Ty>
inline void XMultiWayTree<Ty>::setChild(XMultiWayTree<Ty>* node, const size_t nSel)
{
	if (nSel < 0)//索引不合法
		return;
	if (!isChildIndex(nSel))//索引不存在
	{
		m_ChildList.resize(nSel+1);//先扩容
	}
	m_ChildList[nSel] = node;
}

template<typename Ty>
inline const bool XMultiWayTree<Ty>::removeChild(XMultiWayTree<Ty>* node)
{
	size_t nSel= m_ChildList.indexOf(node);
	if (nSel == -1)
		return false;
	return removeChild(nSel);
}

template<typename Ty>
inline const bool XMultiWayTree<Ty>::removeChild(const size_t nSel)
{
	if(!isChildIndex(nSel))
		return false;
	m_ChildList.remove(nSel, 1);
	return true;
}

template<typename Ty>
inline void XMultiWayTree<Ty>::addData(const Ty& data)
{
	m_DataList.append(data);
}

template<typename Ty>
inline  Ty XMultiWayTree<Ty>::data(const size_t nSel) const
{
	if (!isDataIndex(nSel))
		return Ty();
	return m_DataList[nSel];
}

template<typename Ty>
inline const size_t XMultiWayTree<Ty>::dataSize() const
{
	return  m_DataList.size();;
}

template<typename Ty>
inline const std::vector<Ty>& XMultiWayTree<Ty>::datas() const
{
	return m_DataList;
}

template<typename Ty>
inline void XMultiWayTree<Ty>::setData(const Ty& data, const size_t nSel)
{
	if (!isDataIndex(nSel))
		m_DataList.resize(nSel + 1);//先扩容
	m_DataList[nSel] = data;
}

template<typename Ty>
inline const bool XMultiWayTree<Ty>::removeData(Ty& data)
{
	size_t nSel = m_DataList.indexOf(data);
	if(nSel==-1)
		return false;
	return removeData(nSel);
}

template<typename Ty>
inline const bool XMultiWayTree<Ty>::removeData(const size_t nSel)
{
	if(!isDataIndex(nSel))
		return false;
	m_DataList.remove(nSel, 1);
	return true;
}

template<typename Ty>
inline void XMultiWayTree<Ty>::clearTree() const
{
	std::stack<XMultiWayTree<Ty>*> stack;
	for (auto& child: childs())
	{
		if (child != NULL)
			stack.push(child);
	}
	while (!stack.empty())
	{
		XMultiWayTree<Ty>* node = stack.top();
		stack.pop();
		for (auto& child : node->childs())
		{
			if (child != NULL)
				stack.push(child);
		}
		delete node;
		node = NULL;
	}
}
template<typename Ty>
inline void XMultiWayTree<Ty>::clearTree(XMultiWayTree<Ty>* root)
{
	root->clearTree();
	delete root;
}
template<typename Ty>
inline bool XMultiWayTree<Ty>::isChildIndex(const size_t nSel) const
{
	if (nSel < 0 || nSel >= m_ChildList.size())
		return false;
	return true;
}

template<typename Ty>
inline bool XMultiWayTree<Ty>::isDataIndex(const size_t nSel) const
{
	if (nSel < 0 || nSel >= m_DataList.size())
		return false;
	return true;
}
#endif // !XMultiWayTree_H


